题目描述：

给定一个长度为n的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对；否则不是。

输入格式

第一行包含整数n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

1≤n≤100000

输入样例：

输出样例：

 分析：

本题与AcWing 65 数组中的逆序对是同一题，再次写个题解以加深印象。

与归并排序类似，分而治之。

第一步：将原问题递归的划分为两个子问题L和R；

第二步：递归的求出子问题L和R中逆序对的个数；

第三步：合并子问题的解得到总问题的解。

唯一的问题在于子问题解的合并上，比如L上有x个逆序对，R上有y个逆序对，则LR上的逆序对并不是x与y简单的相加，还要加上两边的逆序对，比如L排好序后是1 3 5，R排好序后是2 4 6，L的排序消除了x个逆序对，R的排序消除了y个逆序对，此时原问题的状态变为1 3 5 2 4 6，可见还是有逆序对存在的，剩下的逆序对需要合并操作来消除。同样比较两个子问题指针指向元素的大小，1 < 2，1是最小的元素，不会存在逆序对，3 > 2,子问题L为1 3 5，既然3都大于2，则有序序列L 3右边的数也都必然大于2，所以L中大于2的数为L的右边界mid减去指向3的指针i加上1，即由2构成逆序对的数目。

本题代码只需在归并排序代码上稍作修改即可得到答案，总的代码如下：